package Simple;

import java.lang.annotation.Target;
import java.util.Arrays;
import java.util.Random;

public class Inversioncount_and_FindPivot {
	/**
	 * 输入一个经过rotated的数组inputs，2分法找到数组中最大的一项的 位置。
	 * 如数组［0,1,2,3］经过变化［2,3,0,1］,返回数值是3的位置＝1
	 * 
	 * @param inputs     a rotated array
	 * @return			  the location of the biggest element of this array
	 */
	public static int find_K(int[] inputs) {
		// add you code here for Q1.
		int end = inputs.length - 1;
		int first = 0;
		int flag = 0;
		if (inputs[end] > inputs[end - 1] && inputs[end] > inputs[first])
			flag = end;
		else {
			while (first < end) {
				flag = (int) Math.floor((first + end) / 2);
				if (inputs[flag] > inputs[flag + 1])
					break;
				else if (inputs[first] > inputs[flag])
					end = flag;
				else
					first = flag + 1;
			}
		}
		return flag;
	}

	/**
	 * 输入一个经过rotated的数组inputs，2分法找到数组中特殊的一项的位置。
	 * @param inputs	a rotated array
	 * @param k			the number need to be found
	 * @return			-1 if k cannot be found
	 * 					else return the location of element whose value is k
	 */
	public static int find_K(int[] inputs, int k) {
		int end = inputs.length - 1;
		int first = 0;
		int flag = 0;
		while(first<=end){
			flag = (first+end)/2;
			if(inputs[flag]==k) return flag;
			if(inputs[first]<=inputs[flag]){
				if(inputs[first]<=k && k<inputs[flag])
					end = flag-1;
				else 
					first = flag+1;
			}
			else{
				if(inputs[flag]<k && k<=inputs[end])
					first = flag+1;
				else
					end = flag-1;
			}
		}
		return -1;
	}

	static int mergecount = 0;
	static int quickcount = 0;
	
	
	public static int inversion2(int[] inputs){
		quicksort(inputs);
		int temp_count = quickcount;
		return temp_count;
	}
	
	public static int[] quicksort(int[] inputs){
		return null;
		
	}
	/**
	 * Count the inversions in an array. e.g, [4,1,0,2] 4>1*2,4>0*2,1>0*2,
	 * return 3
	 * 
	 * @param inputs
	 * @return
	 */
	public static int inversion(int[] inputs) {
		// add you code here for Q2.
		mergesort(inputs);
		int temp_count = mergecount;
		return temp_count;
	}

	public static int[] mergesort(int[] inputs) {
		if (inputs.length == 1)
			return inputs;
		int flag = (int) Math.floor(inputs.length / 2);
		int[] leftarray = Arrays.copyOfRange(inputs, 0, flag);
		int[] rightarray = Arrays.copyOfRange(inputs, flag, inputs.length);
		leftarray = mergesort(leftarray);
		rightarray = mergesort(rightarray);

		// Count for inversions
		int i = 0, j = 0, k = 0;
		int[] after_merge = new int[inputs.length];
		
		while(i<leftarray.length && j< rightarray.length){
			if(leftarray[i] > 2*rightarray[j]) {
				j++;
				// if one element in the left>2 times of rightarray[j]
				// the rest part of leftarray are larger than it.
				mergecount += flag - i;
			} else 
				i++;
		}
		
		//merge two arrays into orders
		i=0;j=0;
		while (i < leftarray.length && j < rightarray.length) {
			if (leftarray[i] < rightarray[j])
				after_merge[k++] = leftarray[i++];
			else {
				after_merge[k++] = rightarray[j++];
			}
		}
		//Copy the left parts
		if (i < leftarray.length) {
			while (k < inputs.length) {
				after_merge[k++] = leftarray[i++];
			}
		}
		if (j < rightarray.length) {
			while (k < inputs.length) {
				after_merge[k++] = rightarray[j++];
			}
		}
		return after_merge;
	}

	public static void main(String[] args) {
		Random random = new Random();
		int pivot = random.nextInt(50);
		System.out.println("The random number k is");
		System.out.println(pivot);
		int[] sorted_array = new int[20];
		for (int i = 0; i < 20; i++) {
			sorted_array[i] = 2 * (i + 1);
		}
		int[] rotated_array = new int[20];
		for (int i = 0; i < 20; i++) {
			rotated_array[i] = sorted_array[(i + pivot) % 20];
		}
		System.out.println("The array after rotation is: ");
		for (int i = 0; i < 20; i++) {
			System.out.print(rotated_array[i] + " ");
		}
		System.out.println("\nThe number k is located in:");
		System.out.println(find_K(rotated_array, pivot));

		int[] testarray = { 10, 3, 2, 0, 1, 4 };
		System.out.println("The test array for counting inversions is:");
		for (int i = 0; i < testarray.length; i++) {
			System.out.print(testarray[i] + " ");
		}
		System.out.println("\nThe number of inversions is:");
		System.out.println(inversion(testarray));
	}
}